/**
 * [64] 最小路径和
 *
 * @format
 * @lc app=leetcode.cn id=64 lang=javascript
 */

// @lc code=start
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
    const [M, N] = [grid.length, grid[0].length]
    const path = []
    for (let i = M - 1; i >= 0; i--) {
        path.push([])
        for (let j = N - 1; j >= 0; j--) {
            let [x, y] = [N - j - 1, M - i - 1]
            if (i == M - 1 && j == N - 1) path[0].push(grid[i][j])
            else if (i == M - 1) path[0].push(grid[i][j] + path[0][x - 1])
            else if (j == N - 1) path[y].push(grid[i][j] + path[y - 1][0])
            else {
                let [a, b] = [path[y - 1][x], path[y][x - 1]]
                path[M - i - 1].push(grid[i][j] + (a < b ? a : b))
            }
        }
    }
    return path[M - 1][N - 1]
}
// debugger
// const grid = [
//     [1, 3, 1],
//     [1, 5, 1],
//     [4, 2, 1]
// ]
// const SHORTEST = minPathSum(grid)
// console.log(SHORTEST)
// @lc code=end
